/*
    created: 2023/4/9
    filename: forward_list.c
    author: 李东霖
    purpose: 单链表的实现和操作的实现
*/

#include"forward_list.h"

//初始化链表，失败返回NULL成功返回链表的头结点，该结点不存放数据
LNode* InitList1()
{
    LinkList head = (LinkList)malloc(sizeof(LNode));
    head->next = NULL;
    return head;
}

//传入指针的地址的初始化方法  
int InitList2(LinkList* phead)
{
    *phead = (LinkList)malloc(sizeof(LNode));
    (*phead)->next = NULL;    
}

//销毁链表
void DestroyList(LinkList *phead)
{
    LNode *temp1 = *phead;
    LNode *temp2;

    *phead = NULL;
    while(temp1 != NULL)
    {
        temp2 = temp1;
        temp1 = temp1->next;
        free(temp2);
    }
}

//清空链表  
void ClearList(LinkList head)
{
    if(head == NULL) return ;
    LNode *p  = head->next;
    LNode *del;
    head->next = NULL;
    while(p != NULL)
    {
        del = p;
        p = p->next;
        free(del);
    }
}

//获得链表的长度 返回值 -1-链表为NULL >=0-链表长度 
int LengthList(LinkList head)
{
    if(head == NULL ) return -1;
    LNode *temp = head;
    int length = 0;
    while(temp->next != NULL)
    {
        temp = temp->next;
        ++length;
    }
    return length;
}

//在链表的第pos个位置插入元素elem 返回值：0-失败 1-成功  
//如果pos大于当前长度则放置在末尾
int InsertList(LinkList head,unsigned int pos, ElemType *elem)
{
    if(pos < 1) return 0;
    if(head == NULL || elem == NULL) return -1;
    LNode *temp = head;
    int loca = 0; 
    //找到前驱  
    while(temp != NULL && loca != pos-1)
    {
        temp = temp->next;
        ++loca;
    }
    LNode *p = (LNode*)malloc(sizeof(LNode));
    if(p == NULL) return 0;
    //考虑到以后会传入结构体
    memcpy(&p->data,elem,sizeof(ElemType));
    p->next = temp->next;
    temp->next = p;
    return 1;
}

//在链表头部插入元素elem  返回值：0-失败 1-成功  
int Push_Front(LinkList head,ElemType *elem)
{
    if(head == NULL) return 0;
    LNode *p = (LNode*)malloc(sizeof(LNode));
    if(p == NULL) return 0;
    //考虑到以后会传入结构体
    memcpy(&p->data,elem,sizeof(ElemType)); 
    LNode *temp  = head->next;
    head->next = p;
    p->next = temp;

    //或者调用InsertList()
}

//在链表尾部插入元素elem  返回值：0-失败 1-成功  
int Push_Back(LinkList head,ElemType *elem)
{
    if(head == NULL) return 0;
    LNode *p = (LNode*)malloc(sizeof(LNode));
    if(p == NULL) return 0;
    //考虑到以后会传入结构体
    memcpy(&p->data,elem,sizeof(ElemType)); 
    LNode *temp  = head;
    while(temp->next != NULL) temp = temp->next;
    temp->next = p;
    p->next = NULL;
    //或者调用InsertList()
}

//打印链表中的全部元素  
void DispList(LinkList head)
{
    if(head == NULL) return;
    LNode* temp = head->next;
    while(temp != NULL)
    {
        printf("%d  ",temp->data);
        temp = temp->next;
    }
}

//删除链表中的第pos个结点 返回值0-失败,pos不合法 1-成功
int DeleteNode(LinkList head,unsigned int pos)
{
    if(pos < 1) return 0;
    if(head == NULL) return -1;
    LNode *temp = head;
    int loca = 0;
    while(temp != NULL && loca != pos -1)
    {
        temp = temp->next;
        ++loca;
    }    
    if(temp == NULL) return 0;
    LNode *del = temp->next;
    temp->next = temp->next->next;
    free(del);
    return 1;

}

//删除链表的头结点 返回值0-失败,链表是空的 1-成功
int Pop_Front(LinkList head)
{
    if(head == NULL ) return -1;
    if(head->next == NULL) return 0;
    LNode* del = head->next;
    head->next = head->next->next;
    free(del);
    return 1;

    //或者调用DeleteNode()
}

//删除链表的尾结点 返回值0-失败,链表是空的 1-成功
int Pop_Back(LinkList head)
{
    if(head == NULL) return -1;
    if(head->next == NULL) return 0; 
    LNode *temp =  head;
    while(temp->next->next != NULL) temp = temp->next;
    free(temp->next);
    temp->next = NULL;
    return 1;
    //或者调用DeleteNode()
}

//判断链表是否为空 返回值：1-空 0-非空
int Is_Empty(LinkList head)
{
    if(head == NULL) return -1;
    if(head->next == NULL) return 1;
    return 0;
}

//获取链表第pos个结点，成功返回该结点，失败返回NULL
LNode* LocateNode(LinkList head,unsigned int pos)
{
    if(head == NULL || head->next ==NULL) return NULL;
    int loca = 0;
    LNode *temp = head;
    while(temp != NULL && loca != pos)
    {
        temp = temp->next;
        ++loca;
    }
    if(temp == NULL) return NULL;
    return temp;
}

//查找元素elem在链表中的位置 没有找到该元素返回NULL，否则返回该结点   
LNode* LocateElem(LinkList head,ElemType *elem)
{
    if(head == NULL || head->next == NULL) return NULL; //链表是空的
    if(elem == NULL) return NULL;
    LNode* temp = head->next;
    while(temp != NULL && temp->data != *elem) temp = temp->next;
    if(temp == NULL) return NULL;
    return temp;    
}

//在指定结点pp之前插入元素elem 返回值：0-失败 1-成功
int InsertPriorNode(LNode *pp,ElemType *elem)
{
    //我们不知道他的前驱，所以我们只能复制数据把pp作为前驱，在它之后再插入
    if(pp == NULL) return 0;
    LNode* temp= (LNode*)malloc(sizeof(LNode));
    if(temp == NULL) return 0;
    memcpy(temp,pp,sizeof(LNode));
    pp->data = *elem;
    pp->next = temp;
    return 1;

}

//在指定结点pp之后插入元素elem 返回值：0-失败 1-成功
int InsertNextNode(LNode *pp,ElemType *elem)
{
    if(pp == NULL) return 0;
    LNode* temp= (LNode*)malloc(sizeof(LNode));
    if(temp == NULL) return 0;
    temp->data = *elem;
    temp->next = pp->next;
    pp->next = temp;
    return 1;
}

//删除指定的结点
int DeleteOneNode(LNode *pp)
{
    //与InsertPriorNode一样，由于不知道前驱所以要复制  
    LNode *tmp=pp->next;  // tmp指向pp的后继结点。
    memcpy(&pp->data,&tmp->data,sizeof(ElemType)); // 把后继结点的数据复制到pp结点中。
    pp->next=tmp->next;   // 把pp的next指向后继结点的next。
    free(tmp);  // 释放后继结点。
    //注意，这是有问题的，如果他是最后一个结点，那么他就没有下个结点。
    //最好还是使用DeleteNode()
    return 1;
}

//归并排序，将传入的两个链表合并为一个新链表(升序)  
int MergeList(LinkList La,LinkList Lb,LinkList Lc)
{
    if(La ==NULL ||Lb ==NULL ||Lc ==NULL) return 0;

    LNode* pp;
    La =La->next;
    Lb = Lb->next;
    while(La != NULL && Lb != NULL)
    {
        // 取La和Lb的较小者。
        if (La->data <= Lb->data)
        {
        pp=La; La=La->next;
        }
        else
        {
        pp=Lb; Lb=Lb->next;
        }       
        Lc->next = (LNode*)malloc(sizeof(LNode));
        Lc = Lc->next;
        Lc->next = NULL;
        memcpy(&Lc->data,&pp->data,sizeof(ElemType));
    }
    // 把链表La其它的元素追加到Lc中。
    while (La != NULL)
    {
    Lc->next=(LNode *)malloc(sizeof(LNode));  // 分配一个新结点。
    Lc=Lc->next;
    memcpy(&Lc->data,&La->data,sizeof(ElemType));
    Lc->next=NULL;
    La=La->next;
    }

    // 把链表Lb其它的元素追加到Lc中。
    while (Lb != NULL)
    {
    Lc->next=(LNode *)malloc(sizeof(LNode));  // 分配一个新结点。
    Lc=Lc->next;
    memcpy(&Lc->data,&Lb->data,sizeof(ElemType));
    Lc->next=NULL;
    Lb=Lb->next;
    }

    return 1;    
}


// 把链表pp结点之后的结点原地逆置（反转），返回值：0-失败；1-成功。
void ReverseList(LNode *pp)
{
    LNode *ss;      // 当前结点。
    LNode *ssnext;  // 当前结点的下一结点。

    ss=pp->next;    // 从pp结点之后的结点开始反转。
    pp->next=NULL;  // pp->next指向空。
    while (ss != NULL)
    {
        ssnext=ss->next;  // 保留ss下一结点的地址。
        // 以下两行相当于在pp之后插入ss结点。
        ss->next=pp->next;  
        pp->next=ss;
        ss=ssnext;  // ss结点后移。
    }
}

